<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="Rzywc" id="Rzywc"><span data-lake-id="u1605fd37" id="u1605fd37">典型回答</span></h1>
  <p data-lake-id="u4678390c" id="u4678390c"><span data-lake-id="ubdd4b4cd" id="ubdd4b4cd">对于HashMap来说，底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，即采用数组+链表/红黑树来解决hash冲突，数组是HashMap的主体，链表主要用来解决哈希冲突。这个数组是Entry类型，它是HashMap的内部类，每一个Entry包含一个key-value键值对</span></p>
  <h2 data-lake-id="hY181" id="hY181"><span data-lake-id="u59520a24" id="u59520a24">get方法</span></h2>
  <p data-lake-id="u1c60c106" id="u1c60c106"><span data-lake-id="u30d91eda" id="u30d91eda">下面是JDK 1.8中HashMap的get方法的简要实现过程：</span></p>
  <ol list="uced920e2">
   <li fid="u78b42e19" data-lake-id="ub2418233" id="ub2418233"><span data-lake-id="ua7180a0c" id="ua7180a0c">首先，需要计算键的哈希值，并通过哈希值计算出在数组中的索引位置。</span></li>
   <li fid="u78b42e19" data-lake-id="ua07e98cc" id="ua07e98cc"><span data-lake-id="ub1ed5fc8" id="ub1ed5fc8">如果该位置上的元素为空，说明没有找到对应的键值对，直接返回null。</span></li>
   <li fid="u78b42e19" data-lake-id="u2fdc3ab5" id="u2fdc3ab5"><span data-lake-id="u73d4ca8a" id="u73d4ca8a">如果该位置上的元素不为空，遍历该位置上的元素，如果找到了与当前键相等的键值对，那么返回该键值对的值，否则返回null。</span></li>
  </ol>
  <p data-lake-id="u9027d82b" id="u9027d82b"><span data-lake-id="u91ec8db7" id="u91ec8db7">​</span><br></p>
  <pre lang="java"><code>
public V get(Object key) {
    Node&lt;K, V&gt; e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
</code></pre>
  <p data-lake-id="u4fcb14da" id="u4fcb14da"><span data-lake-id="ub7fd08b7" id="ub7fd08b7">​</span><br></p>
  <p data-lake-id="u82e054f8" id="u82e054f8"><span data-lake-id="u65bc2179" id="u65bc2179">get 方法看起来很简单，就是通过同样的 hash 得到 key 的hash 值。重点看下 getNode方法：</span></p>
  <p data-lake-id="ub7185f62" id="ub7185f62"><span data-lake-id="u21759309" id="u21759309">​</span><br></p>
  <pre lang="java"><code>
final Node&lt;K, V&gt; getNode(int hash, Object key) {
        //当前HashMap的散列表的引用
        Node&lt;K, V&gt;[] tab;
        //first：桶头元素
        //e：用于存放临时元素
        Node&lt;K, V&gt; first, e;
        //n：table 数组的长度
        int n;
        //元素中的 k
        K k;
        // 将 table 赋值为 tab，不等于null 说明有数据，(n = tab.length) &gt; 0 同理说明 table 中有数据
        //同时将 该位置的元素 赋值为 first
        if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp; (first = tab[(n - 1) &amp; hash]) != null) {
            //定位到了桶的到的位置的元素就是想要获取的 key 对应的，直接返回该元素
            if (first.hash == hash &amp;&amp; ((k = first.key) == key || (key != null &amp;&amp; key.equals(k)))) {
                return first;
            }
            //到这一步说明定位到的元素不是想要的，且该位置不仅仅有一个元素，需要判断是链表还是树
            if ((e = first.next) != null) {
                //是否已经树化
                if (first instanceof TreeNode) {
                    return ((TreeNode&lt;K, V&gt;) first).getTreeNode(hash, key);
                }
                //处理链表的情况
                do {
                    //如果遍历到了就直接返回该元素
                    if (e.hash == hash &amp;&amp; ((k = e.key) == key || (key != null &amp;&amp; key.equals(k)))) {
                        return e;
                    }
                } while ((e = e.next) != null);
            }
        }
        //遍历不到返回null
        return null;
    }

</code></pre>
  <p data-lake-id="u635e0731" id="u635e0731"><span data-lake-id="u6612ef6a" id="u6612ef6a"> </span></p>
  <h2 data-lake-id="PpRpv" id="PpRpv"><span data-lake-id="u60c54a7b" id="u60c54a7b">put方法</span></h2>
  <p data-lake-id="u9de77c95" id="u9de77c95"><span data-lake-id="uacfe5ef0" id="uacfe5ef0">下面是JDK 1.8中HashMap的put方法的简要实现过程：</span></p>
  <ol list="u41e0e2cf">
   <li fid="u3d6a2e1b" data-lake-id="u88b09257" id="u88b09257"><span data-lake-id="ue8203bdc" id="ue8203bdc">首先，put方法会计算键的哈希值(通过调用hash方法)，并通过哈希值计算出在数组中的索引位置。</span></li>
   <li fid="u3d6a2e1b" data-lake-id="ud0ba2b29" id="ud0ba2b29"><span data-lake-id="u2003dafe" id="u2003dafe">如果该位置上的元素为空，那么直接将键值对存储在该位置上。</span></li>
   <li fid="u3d6a2e1b" data-lake-id="u05b37b5c" id="u05b37b5c"><span data-lake-id="u8a9432c8" id="u8a9432c8">如果该位置上的元素不为空，那么遍历该位置上的元素，如果找到了与当前键相等的键值对，那么将该键值对的值更新为当前值，并返回旧值。</span></li>
   <li fid="u3d6a2e1b" data-lake-id="u4bdcacf9" id="u4bdcacf9"><span data-lake-id="uedca92dc" id="uedca92dc">如果该位置上的元素不为空，但没有与当前键相等的键值对，那么将键值对插入到链表或红黑树中（如果该位置上的元素数量超过了一个阈值，就会将链表转化为红黑树来提高效率）。</span></li>
   <li fid="u3d6a2e1b" data-lake-id="u483eca5c" id="u483eca5c"><span data-lake-id="ue361d336" id="ue361d336">如果插入成功，返回被替换的值；如果插入失败，返回null。</span></li>
   <li fid="u3d6a2e1b" data-lake-id="u64aaaa2c" id="u64aaaa2c"><span data-lake-id="u306f4407" id="u306f4407">插入成功后，如果需要扩容，那么就进行一次扩容操作。<br><br></span></li>
  </ol>
  <p data-lake-id="ud9d967e9" id="ud9d967e9"><span data-lake-id="u57d9a6b6" id="u57d9a6b6">​</span><br></p>
  <p data-lake-id="u9dcee894" id="u9dcee894"><span data-lake-id="uf48d46ab" id="uf48d46ab">put方法的代码很简单，就一行代码：</span></p>
  <pre lang="java"><code>
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
</code></pre>
  <p data-lake-id="u58560238" id="u58560238"><br></p>
  <p data-lake-id="ue30939a3" id="ue30939a3"><span data-lake-id="ud4bc3b91" id="ud4bc3b91">核心其实是通过 </span><code data-lake-id="u41b3f973" id="u41b3f973"><span data-lake-id="uab831001" id="uab831001">putValue</span></code><span data-lake-id="ud4705af0" id="ud4705af0">方法实现的，在传给</span><code data-lake-id="u16524b2f" id="u16524b2f"><span data-lake-id="ub0817712" id="ub0817712">putValue</span></code><span data-lake-id="u8913a869" id="u8913a869">的参数中，先调用</span><code data-lake-id="u947d2d30" id="u947d2d30"><span data-lake-id="uc67ae3d7" id="uc67ae3d7">hash</span></code><span data-lake-id="u00e12a91" id="u00e12a91">获取了一下hashCode。</span></p>
  <p data-lake-id="uad8cb495" id="uad8cb495"><br></p>
  <p data-lake-id="u54ebbd80" id="u54ebbd80"><br></p>
  <p data-lake-id="u2889613f" id="u2889613f"><strong><span data-lake-id="u08595118" id="u08595118">putVal 方法主要实现如下，给大家增加了注释：</span></strong></p>
  <p data-lake-id="uf5561dee" id="uf5561dee"><br></p>
  <pre lang="java"><code>
 /**
     * Implements Map.put and related methods.
     *
     * @param hash         key 的 hash 值
     * @param key          key 值
     * @param value        value 值
     * @param onlyIfAbsent true：如果某个 key 已经存在那么就不插了；false 存在则替换，没有则新增。这里为 false
     * @param evict        不用管了，我也不认识
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab 表示当前 hash 散列表的引用
        Node&lt;K, V&gt;[] tab;
        // 表示具体的散列表中的元素
        Node&lt;K, V&gt; p;
        // n：表示散列表数组的长度
        // i：表示路由寻址的结果
        int n, i;
        // 将 table 赋值发给 tab ；如果 tab == null，说明 table 还没有被初始化。则此时是需要去创建 table 的
        // 为什么这个时候才去创建散列表？因为可能创建了 HashMap 时候可能并没有存放数据，如果在初始化 HashMap 的时候就创建散列表，势必会造成空间的浪费
        // 这里也就是延迟初始化的逻辑
        if ((tab = table) == null || (n = tab.length) == 0) {
            n = (tab = resize()).length;
        }
        // 如果 p == null，说明寻址到的桶的位置没有元素。那么就将 key-value 封装到 Node 中，并放到寻址到的下标为 i 的位置
        if ((p = tab[i = (n - 1) &amp; hash]) == null) {
            tab[i] = newNode(hash, key, value, null);
        }
        // 到这里说明 该位置已经有数据了，且此时可能是链表结构，也可能是树结构
        else {
            // e 表示找到了一个与当前要插入的key value 一致的元素
            Node&lt;K, V&gt; e;
            // 临时的 key
            K k;
            // p 的值就是上一步 if 中的结果即：此时的 (p = tab[i = (n - 1) &amp; hash]) 不等于 null
            // p 是原来的已经在 i 位置的元素，且新插入的 key 是等于 p中的key
            //说明找到了和当前需要插入的元素相同的元素（其实就是需要替换而已）
            if (p.hash == hash &amp;&amp; ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
                //将 p 的值赋值给 e
                e = p;
                //说明已经树化，红黑树会有单独的文章介绍，本文不再赘述
            else if (p instanceof TreeNode) {
                e = ((TreeNode&lt;K, V&gt;) p).putTreeVal(this, tab, hash, key, value);
            } else {
                //到这里说明不是树结构，也不相等，那说明不是同一个元素，那就是链表了
                for (int binCount = 0; ; ++binCount) {
                    //如果 p.next == null 说明 p 是最后一个元素，说明，该元素在链表中也没有重复的，那么就需要添加到链表的尾部
                    if ((e = p.next) == null) {
                        //直接将 key-value 封装到 Node 中并且添加到 p的后面
                        p.next = newNode(hash, key, value, null);
                        // 当元素已经是 7了，再来一个就是 8 个了，那么就需要进行树化
                        if (binCount &gt;= TREEIFY_THRESHOLD - 1) {
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    //在链表中找到了某个和当前元素一样的元素，即需要做替换操作了。
                    if (e.hash == hash &amp;&amp; ((k = e.key) == key || (key != null &amp;&amp; key.equals(k)))) {
                        break;
                    }
                    //将e(即p.next)赋值为e，这就是为了继续遍历链表的下一个元素（没啥好说的）下面有张图帮助大家理解。
                    p = e;
                }
            }
            //如果条件成立，说明找到了需要替换的数据，
            if (e != null) {
                //这里不就是使用新的值赋值为旧的值嘛
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null) {
                    e.value = value;
                }
                //这个方法没用，里面啥也没有
                afterNodeAccess(e);
                //HashMap put 方法的返回值是原来位置的元素值
                return oldValue;
            }
        }
        // 上面说过，对于散列表的 结构修改次数，那么就修改 modCount 的次数
        ++modCount;
        //size 即散列表中的元素的个数，添加后需要自增，如果自增后的值大于扩容的阈值，那么就触发扩容操作
        if (++size &gt; threshold) {
            resize();
        }
        //啥也没干
        afterNodeInsertion(evict);
        //原来位置没有值，那么就返回 null 呗
        return null;
    }
</code></pre>
  <p data-lake-id="u034b969e" id="u034b969e"><br></p>
  <h1 data-lake-id="BMQ0j" id="BMQ0j"><span data-lake-id="u07c46497" id="u07c46497">知识扩展</span></h1>
  <h2 data-lake-id="NcFTN" id="NcFTN"><span data-lake-id="ua19c4a45" id="ua19c4a45">HashMap如何定位key</span></h2>
  <p data-lake-id="u1b9c0534" id="u1b9c0534"><span data-lake-id="u042a3123" id="u042a3123">先通过 </span><code data-lake-id="uce17101c" id="uce17101c"><span data-lake-id="u895afa7a" id="u895afa7a">(table.length - 1) &amp; (key.hashCode ^ (key.hashCode &gt;&gt;&gt; 16))</span></code><span data-lake-id="ua05920d9" id="ua05920d9">定位到key位于哪个table中，然后再通过</span><code data-lake-id="u00467160" id="u00467160"><span data-lake-id="u396cdbf6" id="u396cdbf6">key.equals(rowKey)</span></code><span data-lake-id="u3daa362b" id="u3daa362b">来判断两个key是否相同，综上，是先通过hashCode和equals来定位KEY的。</span></p>
  <p data-lake-id="ub7151058" id="ub7151058"><span data-lake-id="ue76eb394" id="ue76eb394">源码如下：</span></p>
  <pre lang="java"><code>
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ...省略
    if ((p = tab[i = (n - 1) &amp; hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    else {
        Node&lt;K,V&gt; e; K k;
        // 这里会通过equals判断
        if (p.hash == hash &amp;&amp; ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(this, tab, hash, key, value);
    // ...省略
    return null;
}
</code></pre>
  <p data-lake-id="u14e49d76" id="u14e49d76"><span data-lake-id="u080285ec" id="u080285ec">所以，在使用HashMap的时候，尽量用String和Enum等已经实现过hashCode和equals方法的官方库类，如果一定要自己的类，就一定要实现hashCode和equals方法</span></p>
  <h3 data-lake-id="Jx4HP" id="Jx4HP"><span data-lake-id="u3b97a384" id="u3b97a384">HashMap定位tableIndex的骚操作</span></h3>
  <p data-lake-id="ubc7a4c35" id="ubc7a4c35"><span data-lake-id="u46dd0b06" id="u46dd0b06">通过源码发现，hashMap定位tableIndex的时候，是通过</span><code data-lake-id="u23f51b5d" id="u23f51b5d"><span data-lake-id="ue878a4be" id="ue878a4be">(table.length - 1) &amp; (key.hashCode ^ (key.hashCode &gt;&gt; 16))</span></code><span data-lake-id="ua56145da" id="ua56145da">，而不是常规的</span><code data-lake-id="u015c4f42" id="u015c4f42"><span data-lake-id="ua287cfa1" id="ua287cfa1">key.hashCode % (table.length)</span></code><span data-lake-id="u6a514eba" id="u6a514eba">呢？</span></p>
  <ol list="u90b1e426">
   <li fid="uc508d03f" data-lake-id="u2e678e25" id="u2e678e25"><span data-lake-id="ubd9e3f38" id="ubd9e3f38">为什么是用&amp;而不是用%：因为&amp;是基于内存的二进制直接运算，比转成十进制的取模快的多。以下运算等价：</span><code data-lake-id="ua167beb3" id="ua167beb3"><span data-lake-id="u3695feac" id="u3695feac">X % 2^n = X &amp; (2^n – 1)</span></code><span data-lake-id="u3829cfec" id="u3829cfec">。这也是hashMap每次扩容都要到2^n的原因之一</span></li>
   <li fid="uc508d03f" data-lake-id="u424b387d" id="u424b387d"><span data-lake-id="uc4bd8f58" id="uc4bd8f58">为什么用key.hash ^ (key.hash &gt;&gt; 16)而不是用key.hash：这是因为增加了扰动计算，使得hash分布的尽可能均匀。因为hashCode是int类型，虽然能映射40亿左右的空间，但是，HashMap的table.length毕竟不可能有那么大，所以为了使hash%table.length之后，分布的尽可能均匀，就需要对实例的hashCode的值进行扰动，说白了，就是将hashCode的高16和低16位，进行异或，使得hashCode的值更加分散一点。</span></li>
  </ol>
  <h2 data-lake-id="qXT74" id="qXT74"><span data-lake-id="u9f5827ce" id="u9f5827ce">HashMap的key为null时，没有hashCode是如何存储的？</span></h2>
  <p data-lake-id="ue1a206d7" id="ue1a206d7"><span data-lake-id="u5b8f41e2" id="u5b8f41e2">HashMap对key=null的case做了特殊的处理，key值为null的kv对，总是会放在数组的第一个元素中，如下源码所示：</span></p>
  <pre lang="java"><code>
private V putForNullKey(V value) {
    for (Entry&lt;K,V&gt; e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}


private V getForNullKey() {
    for (Entry&lt;K,V&gt; e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
</code></pre>
  <h2 data-lake-id="lCDrz" id="lCDrz"><span data-lake-id="u543d363e" id="u543d363e">HashMap的value可以为null吗？有什么优缺点？</span></h2>
  <p data-lake-id="u240a0420" id="u240a0420"><span data-lake-id="u6e99516b" id="u6e99516b">HashMap的key和value都可以为null，优点很明显，不会因为调用者的粗心操作就抛出NPE这种RuntimeException，但是缺点也很隐蔽，就像下面的代码一样：</span></p>
  <pre lang="java"><code>
// 调用远程RPC方法，获取map
Map&lt;String, Object&gt; map = remoteMethod.queryMap();
// 如果包含对应key，则进行业务处理
if(map.contains(KEY)) {
    String value = (String)map.get(KEY);
    System.out.println(value);
}
</code></pre>
  <p data-lake-id="u2352a024" id="u2352a024"><span data-lake-id="u3588baae" id="u3588baae">虽然</span><code data-lake-id="uddb929f2" id="uddb929f2"><span data-lake-id="uad774c1e" id="uad774c1e">map.contains(key)</span></code><span data-lake-id="u519eca7b" id="u519eca7b">，但是</span><code data-lake-id="u5a74a540" id="u5a74a540"><span data-lake-id="ubc3a62e4" id="ubc3a62e4">map.get(key)==null</span></code><span data-lake-id="u4efe4b20" id="u4efe4b20">，就会导致后面的业务逻辑出现NPE问题</span></p>
  <p data-lake-id="u8b23383f" id="u8b23383f"><br></p>
 </body>
</html>